home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-02
/
sortdemo.zip
/
SDSORT06.INC
< prev
next >
Wrap
Text File
|
1992-04-15
|
3KB
|
82 lines
(*
╔═══════════════════════════════════════════════════════════════════════════╗
║ Turbo Pascal 6.0 Include File : SDSORT06.INC ║
╟───────────────────────────────────────────────────────────────────────────╢
║ Program : SORTDEMO.PAS ║
╟───────────────────────────────────────────────────────────────────────────╢
║ Version : 1.0 ║
╟───────────────────────────────────────────────────────────────────────────╢
║ Copyright (c) 1992 by Jon S. Russell ║
╟───────────────────────────────────────────────────────────────────────────╢
║ Quick-Sort #2 routines for SORTDEMO.PAS ║
╚═══════════════════════════════════════════════════════════════════════════╝
*)
procedure QuickSort2 (var Info : InfoType;
First : IndexType;
Last : IndexType);
var
SplitPt1 : IndexType;
SplitPt2 : IndexType;
(*───────────────────────────────────────────────────────────────────────*)
procedure Split (var Info : InfoType;
First : IndexType;
Last : IndexType;
var SplitPt1 : IndexType;
var SplitPt2 : IndexType);
(* Chooses a splitting value and arranges List so that *)
(* List[First] .. List[SplitPt2] <= SplitVal and *)
(* List[SplitPt1+1] .. List[Last] > SplitVal. *)
var
SplitVal : ListElemType;
begin (* Split *)
(* Let SplitVal be the middle value *)
SplitVal := Info.List[(First+Last) div 2];
(* Loop Invariant: elements to the left of First are *)
(* less than or equal to SplitVal; elements to the *)
(* right of Last are greater than SplitVal. *)
repeat
(* Increment First until element > SplitVal. *)
while Info.List[First].Key < SplitVal.Key do
inc(First);
(* Decrement Last until element < SplitVal. *)
while Info.List[Last].Key > SplitVal.Key do
dec(Last);
(* If First and Last are on the wrong side of the split *)
(* point, swap the elements and update First and Last. *)
if First <= Last then
begin
Swap(Info, First, Last);
inc(First);
dec(Last);
end;
until (First > Last);
SplitPt1 := First;
SplitPt2 := Last;
end; (* Split *)
(*───────────────────────────────────────────────────────────────────────*)
begin (* QuickSort2 *)
Info.Sorted := false; (* reset flag *)
if First < Last then
begin
Split(Info, First, Last, SplitPt1, SplitPt2);
if (SplitPt1 < Last) then QuickSort2(Info, SplitPt1, Last);
if (First < SplitPt2) then QuickSort2(Info, First, SplitPt2);
end;
Info.Sorted := true; (* set flag *)
end; (* QuickSort2 *)
(*─────────────────────────────────────────────────────────────────────────*)